#ifndef _BASELIB_WALKER_H
#define _BASELIB_WALKER_H

template<class TTrie>
struct TPathTraits {

    typedef typename TTrie::TInnerStateType TInnerStateType;
    typedef typename TTrie::TInnerChar      TInnerChar;

    struct TPathCell {
        TPathCell( TInnerStateType endOfEdge, TInnerChar transitionChar )
        : EndOfEdge(endOfEdge)
        , TransitionChar(transitionChar)
        {}

        TInnerStateType EndOfEdge;
        TInnerChar      TransitionChar;
    };

    typedef std::vector<TPathCell>    TPath;

};

template<class TTrie, class THandler>
class TTrieWalker {
public:

    typedef typename TTrie::TInnerStateType         TInnerStateType;
    typedef typename TTrie::TInnerChar              TInnerChar;
    typedef typename TPathTraits<TTrie>::TPathCell  TPathCell;
    typedef typename TPathTraits<TTrie>::TPath      TPath;




    TTrieWalker( THandler& handler )
    : PathHandler(handler)
    {}

    void Walk( const TTrie& trie )
    {
        //init path
        TPath           path(1, TPathCell(TTrie::kStartState, TInnerChar(0)));

        while(not path.empty()) {

            RollInLeaf(trie, path);
            //at this state we reach one of leafs
            const TPath&    pathRef(path);
            PathHandler.HandlePath(pathRef);

            RollOutOfeaf(trie, path);
        }
    }

private:

    void RollInLeaf( const TTrie& trie, TPath& path )
    {
        bool            isRolledIn(true);
        TInnerChar      rollChar(TTrie::kMinChar);
        TInnerStateType state(path.back().EndOfEdge);

        //trying to reach leaf
        while (isRolledIn) {
            isRolledIn  =   false;
            bool    isEdgesEnd(false);
            while ((not isRolledIn) and (not isEdgesEnd)) {
                TInnerStateType nextState(trie.Go(state, rollChar));
                if (TTrie::kInvalidState == nextState) {
                    //get next edge
                    if (TTrie::kMaxChar == rollChar) {
                        isEdgesEnd  =   true;
                    }
                    else {
                        ++rollChar;
                    }
                }
                else {
                    //add edge to path
                    isRolledIn  =   true;
                    path.push_back(TPathCell(nextState, rollChar));
                    rollChar    =   TTrie::kMinChar;
                    state       =   nextState;
                }
            }
        }
    }

    void RollOutOfeaf(  const TTrie& trie, TPath& path )
    {
        bool            isRolledOut(false);
        unsigned int    pathSize(path.size());

        while ((1 < pathSize) and (not isRolledOut)) {
            TInnerChar          rollOutChar(path.back().TransitionChar);//using this char we rolled in leaf
            ++rollOutChar;//get next edge

            path.pop_back();//forget about leaf
            --pathSize;

            TInnerStateType     state(path.back().EndOfEdge);//preleaf state
            bool                isEdgesEnd(false);
            while ((not isRolledOut) and (not isEdgesEnd)) {
                TInnerStateType nextState(trie.Go(state, rollOutChar));

                if (TTrie::kInvalidState == nextState) {

                    if (TTrie::kMaxChar == rollOutChar) {
                        isEdgesEnd  =   true;
                    }
                    else {
                        ++rollOutChar;
                    }

                }
                else {
                    isRolledOut =   true;
                    path.push_back(TPathCell(nextState, rollOutChar));//we roll in in node
                    ++pathSize;
                }
            }
        }

        if (not isRolledOut) {
            path.clear();
        }
    }

    THandler&    PathHandler;
};

#endif // _BASELIB_WALKER_H
